伙伴系统
Linux中采用4KB大小的页框作为标准的内存分配单元，在实际应用中，经常需要分配一组连续的页框，而频繁的申请和释放不同大小的连续页框，必然导致在已分配页框的内存块中分散了许多小块的空闲页框，这样，即使这些页框是空闲的，其他需要分配连续页框的应用也很难得到满足。
Linux内核引入了伙伴系统算法来避免这种情况。其把所有的空闲页框分组为11个块链表，每个块链表分别包含大小为1、2、4、8、16、32、64、128、256、512和1024个连续页框的页框块。最大可以申请1024个连续页框，也即4MB大小的连续空间。
假设要申请一个256个页框的块，先从256个页框的链表中查找空闲块，如果没有，就去512个页框的链表中找，找到了即将页框分为两个256个页框的块，一个分配给应用，另外一个移到256个页框的链表中。如果512个页框的链表中仍没有空闲块，继续向1024个页框的链表查找，如果仍然没有，则返回错误。
页框块在释放时，会主动将两个连续的页框块合并成一个较大的页框块。
伙伴算法具有以下一些缺点：
- 一个很小的块往往会阻碍一个大块的合并，一个系统中，对内存块的分配，大小是随机的，一片内存中仅一个小的内存块没有释放，旁边两个大的就不能合并。
- 算法中有一定的浪费现象，伙伴算法是按2的幂次方大小进行分配内存块，当然这样做是有原因的，即为了避免把大的内存块拆的太碎，更重要的是使分配和释放过程迅速。但是他也带来了不利的一面，如果所需内存大小不是2的幂次方，就会有部分页面浪费。有时还很严重。比如原来是1024个块，申请了16个块，再申请600个块就申请不到了，因为已经被分割了。
- 另外拆分和合并涉及到 较多的链表和位图操作，开销还是比较大的。
Buddy算法的分配原理：
假如系统需要4个页面大小的内存块，该算法就到free_area[2]中查找，如果链表中有空闲块，就直接从中摘下并分配出去。如果没有，算法将顺着数组向上查找free_area[3],如果free_area[3]中有空闲块，则将其从链表中摘下，分成等大小的两部分，前四个页面作为一个块插入free_area[2]，后4个页面分配出去，free_area[3]中也没有，就再向上查找，如果free_area[4]中有，就将这16个页面等分成两份，前一半挂入free_area[3]的链表头部，后一半的8个页等分成两等分，前一半挂free_area[2]的链表中，后一半分配出去。假如free_area[4]也没有，则重复上面的过程，知道到达free_area数组的最后，如果还没有则放弃分配。
Buddy算法的释放原理：
内存的释放是分配的逆过程，也可以看作是伙伴的合并过程。当释放一个块时，先在其对应的链表中考查是否有伙伴存在，如果没有伙伴块，就直接把要释放的块挂入链表头；如果有，则从链表中摘下伙伴，合并成一个大块，然后继续考察合并后的块在更大一级链表中是否有伙伴存在，直到不能合并或者已经合并到了最大的块。
Buddy算法对伙伴的定义如下：
- 两个块大小相同；
- 两个块地址连续；
- 两个块必须是同一个大块中分离出来的；
slab机制
slab是Linux系统的一种内存分配机制，其工作是针对一些经常分配并释放的对象，如进程描述符等，这些对象的大小一般比较小，如果直接采用伙伴系统来进行分配和释放，不仅会造成大量的内存碎片，而且处理速度也太慢。而slab分配器是基于对象进行管理的，相同类型的对象归为一类（如进程描述符是一类），每次当要申请这样一个对象，slab分配器就从一个slab列表中分配一个这样大小的单元出去，而当要释放时，将其重新保存到该列表中，而不是直接返回给伙伴系统，从而避免这些内存碎片。slab分配器并不丢弃已分配的对象，而是释放并把它们保存在内存中。当以后又要请求新的对象时，就可以从内存直接获取而不用重复初始化。
说明
本文转载自文章伙伴系统和slab机制。
